#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,A=1e6+5;
int n,T,a[N];
long long searchh(int l,int r){
  long long ans1,ans2;
  if(l>=r)
    return 0;
  int b[N],x,y,pf=l-1,pl=r+1;
  for(int i=l;i<=r;i++)
      b[a[i]]++;
  for(int i=1;i<=A;i++)
    if(i*(b[i]-1)>=ans1)
      ans2=ans1,ans1=i*(b[i]-1),y=x,x=i;
  for(int i=l;i<=r;i++)
    if(i==x||i==y&&pf==l-1){
        pf=i;
        break;
    }
  for(int i=r;i>=l;i--)
    if(i==x||i==y&&pl==r+1){
        pl=i;
        break;
    }
  return ans1+ans2+searchh(l,pf-1)+searchh(pl+1,r);
}
int main(){
  freopen("color.in","r",stdin);
  freopen("color.out","w",stdout);
  scanf("%d",&T);
  for(int t=1;t<=T;t++){
    cin>>n;
    memset(a,0,sizeof(a));
    for(int i=1;i<=n;i++)
      scanf("%d",a[i]);
    cout<<searchh(1,n);
  }
}
